package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         115,
		Discription: "字符串t在字符串s的子序列中出现的次数",
		Level:       3,
		Labels: map[string]int{
			"动态规划": 1,
			"字符串":  1,
		},
	})
}

func NumDistinct(s string, t string) int {
	m := len(s)
	n := len(t)
    //dp[i][j]表示s[:i]中有多少个子序列能和t[:j]匹配
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][0] = 1
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s[i-1] == t[j-1] {
                //dp[i-1][j-1]表示用了s[i-1] == t[j-1]，dp[i-1][j]表示不用
				dp[i][j] = dp[i-1][j-1]
			}
			dp[i][j] += dp[i-1][j]
		}
	}

	return dp[m][n]
}
